import java.util.Arrays;
import java.util.Random;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {5, 3, 3, -40, 3, 2, 1};
        int[] divide = betterPartition(arr, 0, arr.length - 1, 3);
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (arr == null || left >= right) {
            return;
        }

        // 哨兵位置
        int pivot = arr[left + new Random().nextInt(right - left + 1)];
//        int adjustIndex = partition(arr, left, right, pivot);
//        int leftEnd = adjustIndex - 1;
//        int rightStart = adjustIndex + 1;

        int[] divide = betterPartition(arr, left, right, pivot);

        quickSort(arr, left, divide[0] - 1);
        quickSort(arr, divide[1] + 1, right);
    }

    private static int partition(int[] arr, int left, int right, int pivot) {

        int pivotIndex = left;
        int smallIndex = left;
        int bigIndex = left;

        while (bigIndex <= right) {
            if (arr[bigIndex] <= pivot) {
                swap(arr, smallIndex, bigIndex);
                // 记录哨兵位置
                if (arr[smallIndex] == pivot) {
                    pivotIndex = smallIndex;
                }
                smallIndex++;
                bigIndex++;
            } else if (arr[bigIndex] > pivot) {
                bigIndex++;
            }
        }
        // 保证分界处是哨兵值
        swap(arr, pivotIndex, smallIndex - 1);

        return smallIndex - 1;
    }

    private static int[] betterPartition(int[] arr, int left, int right, int pivot) {
        // 不包含 小于的区间 [left, smallEndIndex)
        int smallEndIndex = left;       // 待交换的下标
        int bigStartIndex = right;

        for (int i = left; i <= bigStartIndex; i++) {
            if (arr[i] < pivot) {
                swap(arr, smallEndIndex, i);
                smallEndIndex++;
            } else if (arr[i] > pivot) {
                swap(arr, bigStartIndex, i);
                bigStartIndex--;
                // 交换后，i位置的数字可能大于哨兵值
                i--;
            }
        }
        return new int[]{smallEndIndex, bigStartIndex};
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
